﻿#define DEBUG_LOG

using System;
using System.Collections.Generic;
using System.Text;

namespace 树
{
    
    /// <summary>
    /// AVL树 (以发明人的Initial命名)
    /// Balanced Binary Search Tree
    /// 平衡二叉搜索树
    /// AVL Tree = BBST
    /// </summary>
    /// <typeparam name="T">AVL树中要包含的用户数据类型</typeparam>
    class BST<T> where T : IComparable<T>
    {
        public const int AVL_IMBA_LEFT   = 1;
        public const int AVL_IMBA_RIGHT  = -1 * AVL_IMBA_LEFT;
        public const int BBST_IMBA_LEFT  = AVL_IMBA_LEFT;
        public const int BBST_IMBA_RIGHT = AVL_IMBA_RIGHT;

        /// <summary>
        /// 左树高度
        /// </summary>
        //public int HeightLeft { get; protected set; } //这种方式不用每次都计算
        public int HeightLeft { get => GetHeight(root.ChildLeft); }

        /// <summary>
        /// 右树高度
        /// </summary>
        public int HeightRight { get => GetHeight(root.ChildRight); }

        /// <summary>
        /// 总高度
        /// </summary>
        public int Height { get => Math.Max(HeightLeft, HeightRight); }

        /// <summary>
        /// 总节点数
        /// </summary>
        public int NodeNum { get; protected set; }

        public bool Balance { get; set; }

        private BSTNode<T> root;
        
        public BST()
        {
            root = new BSTNode<T>();
        }

        public BST(BSTNode<T> node)
        {
            root = node;
        }

        public BSTNode<T> Insert(T t) { return Add(t); }

        public BSTNode<T> Add(T t)
        {
            // 如果是空树，直接插在根节点并返回不需要检查平衡性
            if (root.Data == null)
            {
                root.Data = t;
                return root;
            }

            // tempNode当前遍历的节点，tempParent为tempNode的Parent，只为了在出循环的时候设置互链
            BSTNode<T> tempNode = root;
            BSTNode<T> tempParent = root;
            int compare = 0, height = 0; ;

            // 当前遍历节点不为空，一直按规则比较直到找到合适插入的点
            while (tempNode != null)
            {
                compare = t.CompareTo(tempNode.Data);
                // 如果Key值已经存在，插入失败返回-1
                if (compare == 0) return tempNode;
                tempParent = tempNode;
                tempNode = compare > 0 ? tempNode.ChildRight : tempNode.ChildLeft;
                height++;
            }
            // 出了while表示此时tempNode是一个符合插入条件的空节点，tempParent是其父节点

            // 将新插入的数据T t，新建AVLNode并与其Parent互链
            tempNode = new BSTNode<T>(t);
            if (compare > 0)
                tempParent.ChildRight = tempNode; 
            else
                tempParent.ChildLeft = tempNode;
            tempNode.Parent = tempParent;
            BSTNode<T> ret = tempNode;

            // 插入完成后进行平衡因子检查，如果不平衡需要进行相应旋转树
            if (!Balance)
            {
                NodeNum++;
                return ret;
            }
            
            while (tempParent != null)
            {
                // 插入右边因子-1，左边+1
                if (tempParent.ChildLeft == tempNode)
                    tempParent.BalanceFactor += AVL_IMBA_LEFT;
                else
                    tempParent.BalanceFactor += AVL_IMBA_RIGHT;

                // 不需要调整平衡
                if (tempParent.BalanceFactor == 0)
                {
#if DEBUG_LOG
                    Console.WriteLine("插入节点{0}，平衡未变化", ret.ToString());
#endif
                    break;
                }
                    
                // 继续向上(根节点方向)查询
                else if (tempParent.BalanceFactor == AVL_IMBA_LEFT || tempParent.BalanceFactor == AVL_IMBA_RIGHT)
                {
                    tempNode = tempParent;
                    tempParent = tempNode.Parent;
                }
                else // 2 or -2
                {
                    if (tempParent.BalanceFactor == AVL_IMBA_LEFT * 2)
                    {
                        if (tempNode.BalanceFactor == AVL_IMBA_LEFT)
                        {
#if DEBUG_LOG
                            Console.WriteLine("向{0}节点插入{1}节点，围绕{0}节点进行LL旋转", tempNode.ToString(), ret.ToString());
                            DebugPrint(1);
#endif
                            RotateLL(tempParent);
                        }
                        else
                        {
#if DEBUG_LOG
                            Console.WriteLine("向{0}节点插入{1}节点，围绕{0}节点进行LR旋转", tempNode.ToString(), ret.ToString());
                            DebugPrint(1);
#endif
                            RotateLR(tempParent);
                        }
                        
                    }
                    else
                    {
                        if (tempNode.BalanceFactor == AVL_IMBA_LEFT)
                        {
#if DEBUG_LOG
                            Console.WriteLine("向{0}节点插入{1}节点，围绕{0}节点进行RL旋转", tempNode.ToString(), ret.ToString());
                            DebugPrint(1);
#endif
                            RotateRL(tempParent);
                        }
                        else
                        {
#if DEBUG_LOG
                            Console.WriteLine("向{0}节点插入{1}节点，围绕{0}节点进行RR旋转", tempNode.ToString(), ret.ToString());
                            DebugPrint(1);
#endif
                            RotateRR(tempParent);
                        }
                    }
                    break;
                }
            }
            NodeNum++;
            return ret;
        }

        public int Remove(T t)
        {

            return 0;
        }

        public T Get(int key)
        {

            return default(T);
        }

        public void DebugPrint(int 节点字符数)
        {
            BSTNode<T>[] 行节点;
            int 最高层节点数 = (int)Math.Pow(2, Height) * 2;
            Console.WriteLine("----------------------------start tree----------------------------");
            // 行高循环
            for (int 行Index = 0; 行Index <= Height; 行Index++)
            {
                行节点 = GetParallelNodes(行Index);
                int 行节点数 = (int)Math.Pow(2, 行Index);
                char[] 行内容 = new char[最高层节点数 * 节点字符数];

                for (int x = 0; x < 行内容.Length; x++)
                    行内容[x] = ' ';

                // 行内循环
                for (int 节点Index = 0; 节点Index < 行节点数; 节点Index++)
                {
                    int 打印Index = GetDisplayIndex(节点Index, 行Index, Height);
                    string 节点内容 = 行节点[节点Index] == null ? "" : 行节点[节点Index].ToString();
                    节点内容.ToCharArray().CopyTo(行内容, 打印Index * 节点字符数);
                }
                Console.WriteLine(new string(行内容));
                
            }
            Console.WriteLine("----------------------------end tree----------------------------");
            Console.WriteLine();
            Console.WriteLine();
        }

        #region 内部自旋转
        private void RotateLL(BSTNode<T> parent)
        {
            BSTNode<T> oldLeft = parent.ChildLeft;
            BSTNode<T> oldSubRight = oldLeft.ChildRight;
            oldLeft.Parent = parent.Parent;
            //if (parent.Parent != null)
            //{
            //    if (parent == parent.Parent.ChildLeft)
            //        parent.Parent.ChildLeft = oldLeft;
            //    else
            //        parent.Parent.ChildRight = oldLeft;
            //}
            oldLeft.ChildLeft = oldLeft.ChildLeft;
            oldLeft.ChildRight = parent;
            parent.ChildLeft = oldSubRight;
            parent.Parent = oldLeft;
            oldLeft.BalanceFactor = 0;
            parent.BalanceFactor = 0;
            if (parent == root)
                root = oldLeft;
        }

        private void RotateRR(BSTNode<T> parent)
        {
            BSTNode<T> oldRight = parent.ChildRight;
            BSTNode<T> oldSubLeft = oldRight.ChildLeft;
            oldRight.Parent = parent.Parent;
            //if (parent.Parent != null)
            //{
            //    if (parent == parent.Parent.ChildLeft)
            //        parent.Parent.ChildLeft = oldRight;
            //    else
            //        parent.Parent.ChildRight = oldRight;
            //}


            oldRight.ChildRight = oldRight.ChildRight;
            oldRight.ChildLeft = parent;
            parent.ChildRight = oldSubLeft;
            parent.Parent = oldRight;
            parent.BalanceFactor = 0;
            oldRight.BalanceFactor = 0;
            if (parent == root)
                root = oldRight;
        }

        private void RotateLR(BSTNode<T> parent)
        {
            RotateRR(parent.ChildLeft);
            RotateLL(parent);
        }

        private void RotateRL(BSTNode<T> parent)
        {
            RotateLL(parent.ChildRight);
            RotateRR(parent);
        }
        #endregion 

        /// <summary>
        /// 辅助打印显示AVL树，[递归]获取这个节点应该打印在第几个位置Index
        /// </summary>
        /// <param name="Index">该高度上的从左到右第几个</param>
        /// <param name="CurrentHeight">当前层高</param>
        /// <param name="MaxHeight">树高度</param>
        /// <returns></returns>
        private int GetDisplayIndex(int Index, int CurrentHeight, int MaxHeight)
        {
            if (CurrentHeight == MaxHeight)
                return Index * 2 + 1;
            return GetDisplayIndex(Index * 2, CurrentHeight + 1, MaxHeight) 
                + (int)Math.Pow(2, (MaxHeight - CurrentHeight - 1));
        }

        /// <summary>
        /// 辅助打印显示AVL树，[递归]获取同一个高度上的节点集合
        /// </summary>
        /// <param name="height">0=root,依次递增</param>
        /// <returns>该高度上的节点集合数组，从左到右</returns>
        private BSTNode<T>[] GetParallelNodes(int height)
        {
            // 递归到第一层，返回根节点
            if (height == 0) return new BSTNode<T>[] { root };
            // 当前层节点数量(包含空节点)
            int num = (int)Math.Pow(2, height);
            // ret返回值，upLevel上一层节点
            BSTNode<T>[] ret = new BSTNode<T>[num];
            BSTNode<T>[] upLevel = GetParallelNodes(height - 1);
            // 当前层 = 上一层的Left/Right
            for (int i = 0; i < num; i += 2)
            {
                ret[i] = upLevel[i / 2]?.ChildLeft;
                ret[i + 1] = upLevel[i / 2]?.ChildRight;
            }
            return ret;
        }

        private int GetHeight(BSTNode<T> node)
        {
            if (node == null) return 0;
            int l = GetHeight(node.ChildLeft);
            int r = GetHeight(node.ChildRight);
            return Math.Max(l, r) + 1;
        }

        
    }
}
